// https://www.lintcode.com/problem/space-replacement/

public class Solution {
    /*
     * @param string: An array of Char
     * @param length: The true length of the string
     * @return: The true length of new string
     */
    public int replaceBlank(char[] string, int length) {
        // write your code here
        int new_length = length; // 先数替换所有空格后的长度
        for (int i = 0; i < length; ++i) {
            if (' ' == string[i]) {
                new_length += 2;
            }
        }
        int idx = new_length;
        for (int i = length - 1; i >= 0; --i) {
            if (string[i] != ' ') {
                --idx;
                string[idx] = string[i]; // 填入非空格内容
            }
            else {
                idx -= 3; // 给增加的字符腾出空间
                string[idx] = '%';
                string[idx + 1] = '2';
                string[idx + 2] = '0';
            }
        }
        return new_length;
    }
}